﻿namespace Algo.Sort
{
    using System.Collections.Generic;

    internal sealed class QuickSortStrategy : ISortStrategy
    {
        public IEnumerable<T> Sort<T>(IEnumerable<T> items, IComparer<T> comparer, IAlgoExtensions extensions)
        {
            var list = SortUtilities.CopyToList(items);
            if (list.Count <= 1)
            {
                return list;
            }

            Sort(list, comparer, 0, list.Count - 1, extensions);
            return list;
        }

        private static void Sort<T>(IList<T> list, IComparer<T> comparer, int left, int right, IAlgoExtensions extensions)
        {
            var midItem = list[(left + right) / 2];
            var curLeft = left;
            var curRight = right;
            var iterationsCount = 0;
            do
            {
                while (SortUtilities.IsGreaterThen(comparer, midItem, list[curLeft]))
                {
                    curLeft++;
                }

                while (SortUtilities.IsGreaterThen(comparer, list[curRight], midItem))
                {
                    curRight--;
                }

                if (curLeft <= curRight)
                {
                    SortUtilities.Swap(list, curLeft, curRight);
                    curLeft++;
                    curRight--;
                }

                iterationsCount++;
            }
            while (curLeft < curRight);

            IMetricsExtension metricsBehaviour;
            if (extensions.TryGet(out metricsBehaviour))
            {
                metricsBehaviour.RegisterIterations(iterationsCount);
            }

            if (curRight > left)
            {
                Sort(list, comparer, left, curRight, extensions);
            }

            if (curLeft < right)
            {
                Sort(list, comparer, curLeft, right, extensions);
            }
        }
    }
}
